package com.ruijixiang.leetcode.weekly.leetcode2024.leetcode20241013;


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class leetcode3319 {

    /**
     * 第k大的完美二叉树的大小
     * @param root
     * @param k
     * @return
     */
    public int kthLargestPerfectSubtree(TreeNode root, int k){
        List<Integer> hs=new ArrayList<>();
        dfs(root,hs);

        if(k>hs.size()){
            return -1;
        }
        Collections.sort(hs);
        return (1<<hs.get(hs.size()-k))-1;
    }

    private int dfs(TreeNode node,List<Integer> hs){
        if(node==null){
            return 0;
        }
        int leftH=dfs(node.left,hs);
        int rightH=dfs(node.right,hs);
        if(leftH<0 || leftH!=rightH){
            return -1;
        }
        hs.add(leftH+1);
        return leftH+1;
    }
}
